The speed of complex machines is commonly determined by the time delay of electrical signals through their electronic components. In the process of designing a machine of certain speed, particular attention is given to the critical paths, since they are the ones that determine the machine cycle and help define how fast a machine can run. Attempts to minimize a machine cycle by improving the performance of circuits does not by itself guarantee a faster machine. Other considerations (independent of the functional circuit delay) pertaining to layout, such as chip or floor planning, partitioning, placement and wire routing have played an ever increasing role in the design of machines. As a result, it is not uncommon to find a small number of data paths with excessive delay playing an important role in limiting the machine cycle of a computing machine. Considerable effort has been expended by design practitioners in optimizing data paths by minimizing length so as to reduce wire capacitance and resistance and the distance for a signal to travel.
An example of how a logic function comprised of a plurality of interconnected blocks may be decomposed into constituent paths, such as signal paths, machine paths, etc., and a determination of relative path delay value extremes for each path is described in U.S. Pat. No. 4,263,651 to W. E. Donath et al and of common assignee.
In another instance, such as U.S. Pat. No. 4,564,943 to J. C. Collins et al, and of common assignee, delay paths are stressed for their extremes to assist in the characterization of a design that is to be frozen. No attempt, though is made to optimize the overall timing.
In U.S. Pat. No. 4,698,760 to R. E. Lembach and of common assignee, optimization of the signal timing delay is arrived at by actually altering the circuit block through the selection of different logic book types. This method does not address timing optimization by placement and partitioning methods.
Heuristic techniques which explore the permutation space of all possible block placements must conduct their trial and error search by using a guiding or goal oriented mechanism called `cost` or `objective` function. Several papers in various publications have been published, whereby attempts to minimize the `cost` function have been made:
"Optimization by Simulated Annealing", by S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science, Vol. 220, No. 4598, pp. 671-680. This highlights the connection that exists between statistical mechanics and combinatorial optimization. It discusses the strong analogy with annealing in solids, thus providing a framework for optimizing the properties of very large and complex systems. This approach does not formulate Constructive Placement algorithms for initial placement or address timing optimization of specific critical paths and geometric constraints of path segments. Moreover, it does not provide interactive guidance for defining the assumptions required for initial conditions--such as partitioning boundaries, modelling and optimization of a complete machine.
"ESP: Placement by Simulated Evolution", by R. M. Kling and P. Banerjee, IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems, (1989), Vol 8, No. 3, pp. 245-256 discloses a method which is similar to the previous reference but uses a different heuristic algorithm that involves multiple block relocations as opposed to pair swapping. Even though it is a method of simulating an evolutionary process that effectively minimizes cell interconnection length, it contains the same limitations as the previous approach.
"Genetic Placement", by J. P. Cohoon and W. D. Paris, 1986 IEEE Intl. Conference on Computer Aided Design, pp. 422-425, is similar to the two previous approaches and with the same limitations.
"A new Approach for Solving the Placement Problem using Force Models", by K. J. Antreich, F. M. Johannes and F. H. Kirsch, IEEE International Symposium on Circuits and Systems, June 1982, pp. 481-486 discloses a Force Model using pair swapping just as in Simulated Annealing and iterates to a solution as in all previously mentioned cases. Its cost function is based on modelling of interconnection's affinities as a function of the forces of attraction and repulsion between blocks until equilibrium is reached. Again, the same limitations are found.
"Stochastic Evolution: A Fast Effective Heuristic for some Generic Layout Problems" by Y. G. Saab & V. B. Rao, Proceedings of the 27th Design Automation Conference, 1990, pp. 26-31 is another heuristic technique that seeks faster solution results and better quality than that found in Simulated Annealing. It operates on the principle that states are deemed suitable for survival based on an evaluation by the cost function. Its algorithm includes backtracking of proposed block moves if changes are deemed unsuitable for survival. Once again, the same limitations as previously mentioned are found.
Most importantly, all of the referenced publications collectively attempt to achieve a faster machine solution by minimizing total wiring or capacitance of the nets within a machine architecture. No systematic procedure exists for determining the priority of block placement based on how critical certain signal paths may be or the geometric constriction of their `net segments`. None of the previously described approaches offer an initial placement strategy or guidance to assist in the human decision process where judgement involving partitioning and I/O constraints force certain initial conditions that reside outside the purview of the method of placement. Thus, a faster machine cannot be guaranteed when the algorithms that carry out an optimization are based on total wire, total capacitance or some other summation parameter. One may arrive at a placement scenario which may have the least amount of total wire or capacitance but which results in a slower machine than some other placement with greater wire or capacitance. This can occur when the machine speed is limited by the longest path and not by the largest amount of wire or capacitance.
Most heuristic placement algorithms presently operate with a variety of `cost` or `objective` functions as found in the above described Simulated Annealing and Genetic Placement methods. Some, such as `Min-Cut`, attempt to minimize wire congestion and channel competition by intelligent placement. Others, such as `Bounded Rectangle`, `Concentric Circle`, and `Position Oriented` seek to improve machine cycle and performance by minimizing total wire or total capacitance. These timing directed functions share a common factor in that they are all net oriented, handling all segments of a given net as one net entity.